//
// Created by TianBo on 2022/6/3.
//

/*
 *有n个打包机器人从左到右一字排开，上方有一个自动装置会抓取一批物品放到每个打包机器上
 *放到每个机器上的物品数量有多有少，由于物品数量不相同，需要工人将每个机器上的物品进行
 *移动从而到达物品数量相等才能打包。
 *每个物品重量太大，每次只能搬一个物品进行移动，为了省力，只能在相邻的机器上移动。请计算
 *在搬动最小轮数的前提下，使每个机器上的物品数量相等。如不能使每个机器上的物品数量相等，
 * 则返回-1。
 * 例：[1,0,5]
 * 需经过三轮移动
 * 第一轮：[1,1,4]   第二轮：[2,1,3]   第三轮：[2,2,2]
 */

/*
 * 解题思路：
 * 属于业务题(死记硬背型)
 * 贪心
 * 遍历每一个机器，然后以该位置为基准，判断左边 所拥有的物品数量 - 实际需要的物品数量(记为：leftCount)   和  右边  所拥有的物品数量 - 实际需要的物品数量(记为：rightCount)
 * if(leftCount < 0 && rightCount < 0) 说明基准位置物品多，则需要(leftCount + rightCount)轮 才能满足需求
 * if((leftCount > 0 && rightCount >0) || (leftCount < 0 && rightCount >0) || (leftCount > 0 && rightCount < 0)) ，则需要 max(leftCount,rightCount)轮 才能满足需求
 */

#include "iostream"
#include "vector"

using namespace std;

class Solution{
public:
    int moveCount(vector<int>& items){
        int sum = 0;
        for(auto item:items)
            sum += item;
        if(sum % items.size() != 0)
            return -1;
        int avg = sum / items.size();
        int res = 0;
        int leftSum = 0,rightSum = 0;
        int rightCount,leftCount;

        for (int i = 0; i < items.size(); ++i) {
            rightSum = sum - leftSum - items[i];
            leftCount = leftSum - i * avg;
            rightCount = rightSum - (items.size() - 1 - i) * avg;
            if(leftCount < 0 && rightCount < 0)
                res = max(res,abs(leftCount) + abs(rightCount));
            else
                res = max(res,max(abs(leftCount),abs(rightCount)));
            leftSum += items[i];
        }
        return res;
    }
};

int main()
{
    Solution s;
    vector<int> items{1,0,5};
    cout<<s.moveCount(items)<<endl;
    return 0;
}